#!/usr/bin/python
# -*- coding: utf8 -*-

from nodos_gramatica import *
from parser_gramatica import gramatica
import pyparsing

from sets import Set
import re

# Expresiones regulares útiles (a falta de tokenizer)
re_whitespace = re.compile(r'\s')
charsvalidos = 'abcdefghijklmnopqrstuvwxyz' + \
               'ABCDEFGHIJKLMNOPQRSTUVWXYZ' + \
               ':;?*+|()'
re_terminal = re.compile(r'[a-z]')
re_noterminal = re.compile(r'[A-Z]')

# Aliases para simplificar el código del parser
match_nt = re_noterminal.match
match_t = re_terminal.match



################################
# Excepciones                  #
################################

class EmptyInputError(Exception):
    pass


class InputError(Exception):
    def __init__(self, linea, numlinea, s, char=None):
        self.linea = linea
        self.numlinea = numlinea
        self.char = char
        self.s = s

    def __str__(self):
        if self.char is None:
            if len(self.linea) > 0:
                return "Error en la gramática\n" + \
                       "\n" + \
                       "Producción: %s\n" % self.numlinea + \
                       "%s\n" % self.s + \
                       "Ubicación: %s\n" % self.linea
            else:
                return "Error en la gramática\n" + \
                       "\n" + \
                       "Producción: %s\n" % self.numlinea + \
                       "%s\n" % self.s
        else:
            return "Error en la gramática\n" + \
                   "\n" + \
                   "Producción: %s\n" % self.numlinea + \
                   "%s\n" % self.s + \
                   "Se recibió: '%s'\n" % self.linea[self.char] + \
                   "Ubicación: %s\n" % self.linea + \
                   (" " * (11 + self.char)) + '^'


class ParseError(Exception):
    def __init__(self, e):
        self.e = e
    
    def __str__(self):
        return str(self.e) + "\n" + \
               "Ubicación: " + self.e.line + "\n" + \
               (" " * (10 + self.e.col)) + "^"


class NodoNoEncontrado(Exception):
    pass

################################
# Clase GramaticaELL1          #
################################

class GramaticaELL1:
    def __init__(self, s):
        '''Inicializa la gramática a partir de un string o un objeto
           file-like conteniendo las producciones en el formato apropiado'''
        try:
            self.texto = s.read()
        except AttributeError:
            try:
                self.texto = str(s)
            except:
                raise ValueError("Se esperaba un objeto file o un string")
        
        self.terminales = Set()
        self.noTerminales = Set()
        self.producciones = {}
        self.simboloDistinguido = None
     

        self._cargar()


    def __repr__(self):
        return ''.join(['GramáticaELL1 object at %s' % hex(id(self)),
                      '\nNo terminales: ', repr(list(self.noTerminales)),
                      '\nTerminales: ', repr(list(self.terminales)),
                      '\nDistinguido: ', repr(self.simboloDistinguido),
                      '\nProducciones: ', repr(self.producciones)
                       ])


    def _limpiar_whitespace(self, s):
        '''Limpia self.texto de espacios en blanco, tabs y saltos de línea'''
        return re_whitespace.sub('', s)


    def _validar_chars(self):
        '''Valida que self.texto contenga únicamente caracteres válidos'''
        i = 0
        for l in self.texto.split('\n'):
            i = i + 1
            for c in self._limpiar_whitespace(l):
                if not (c in charsvalidos):
                    raise InputError(l, i, "La gramática contiene caracteres inválidos!")


    def _cargar_simbolos(self):
        '''Carga los conjuntos de símbolos y hace una validación preliminar'''
        # Separo por ";" y elimino el último elemento
        # (asumo que la gramática termina en un ";", por
        # lo que el último elemento es la cadena vacía.
        try:
            lineas = self.texto.split(';')
            lineas.pop()
            assert(len(lineas) > 0)
        except (IndexError, AssertionError):
            raise EmptyInputError("Se esperaba al menos una producción en la gramática!")
        
        # Elimino espacios innecesarios en cada línea
        lineas = [self._limpiar_whitespace(l) for l in lineas]

        # Valido que solo haya caracteres validos
        self._validar_chars()

        # Valido que la gramática sea libre de contexto
        # (esto es, que cada producción sea la forma NT:<...>,
        # donde NT es un no terminal.
        i = 0
        for l in lineas:
            i = i+1
            if l == "":
                raise InputError(l, i, "Se esperaba un no terminal!")
            elif  match_nt(l[0]) is None:
                raise InputError(l, i, "Se esperaba un no terminal!", char=0)
            elif l[1] != ':':
                raise InputError(l, i, "Se esperaba ':' (la gramática debe ser libre de contexto)!", char=1)

        # Cargo el símbolo distinguido
        l = lineas[0]
        self.simboloDistinguido = l[0]

        # Cargo los símbolos en los conjuntos correspondientes.
        i = 0
        for l in lineas:
            i = i+1
            try:
                nt, resto = l.split(':')
            except ValueError:
                raise InputError(l, i, "Se necesita exactamente un ':' por línea de la gramática!")
                
            self.terminales.union_update(Set(re_terminal.findall(resto)))
            self.noTerminales.union_update(Set(re_noterminal.findall(resto)))
            self.noTerminales.add(nt)

    
    def _cargar(self):
        '''Analiza sintácticamente la gramática propuesta y produce un árbol
           de parsing con una representación de la misma'''

        self._cargar_simbolos()
        p = ParserGramatica(self.texto)
        
        # Chequeo que todos los no terminales que aparecen en
        # las producciones tengan una producción asociada.
        for nt in self.noTerminales:
            self.producciones[nt] = None
        
        if Set(p.producciones.keys()) != Set(self.producciones.keys()):
            indefinidos = [x for x in self.producciones.keys() if not x in p.producciones.keys()]
            raise GrammarError("Los siguientes no terminales no están definidos: %s" % indefinidos,None)
        
        # Parseo la gramática y cargo los árboles de producción
        self.producciones = p.producciones

    def nodos(self):
        '''Devuelve el conjunto de todos los nodos del árbol de parsing'''
        nodos = Set()
        nodos.union_update(Set([SimboloNoTerminal(s) for s in self.noTerminales]))

        lista_aplastados = [self.producciones[nt].aplastar() for nt in self.noTerminales]
        nodos_aplastados = Set()
        for a in lista_aplastados:
            nodos_aplastados.union_update(a)
        nodos.union_update(nodos_aplastados)

        return nodos
    
    def alcanzables(self):
        '''Devuelve el conjunto de todos los símbolos no terminales
           alcanzables de la gramática'''
        res = Set()
        res.add(self.simboloDistinguido)
        cambio = True
        while(cambio):
            cambio = False
            aux = Set()
            for nt in res:
                for simbolo in self.noTerminales:
                    nodo = SimboloNoTerminal(simbolo)
                    if self.producciones[nt].perteneceSubArbol(nodo):
                       aux.add(simbolo)
            if not aux.issubset(res):
                cambio = True
                res.union_update(aux)
        return res
                
    def buscarNTAsociado(self, nodo):
        '''Busca un no terminal cuya producción asociada contenga en algún
           lugar al nodo recibido. En caso de no encontrar ninguno, lanza una
           excepción'''
        for nt in self.noTerminales:
            if self.producciones[nt].perteneceSubArbol(nodo):
                return nt            
        
        # Puede ser que el nodo sea un no terminal y solo esté como raíz
        if isinstance(nodo, SimboloNoTerminal) and nodo.simbolo == nt:
            return nt
                
        raise NodoNoEncontrado("El nodo no pertenece a la gramática!")
            
    def generarDot(self):
        s = "Digraph g{\n"
        for nt in self.noTerminales:
            s += str(id(nt))+'[label="'+nt+'"];\n'
            if(self.simboloDistinguido == nt):
                s += str(id(nt))+'[color=green,style=filled];\n'
            s+= str(id(nt)) + "->" +str(id(self.producciones[nt])) + ";\n"
            s+= self.producciones[nt].generarDot()
        s+="}\n"
        return s
            
            
        

################################
# Clase ParserGramatica        #
################################

class ParserGramatica:
    def __init__(self, texto):
        self.producciones = {}

        try:
            lineas = gramatica.parseString(texto)
        except pyparsing.ParseException, e:
            raise ParseError(e)

        # Cargo el diccionario de producciones con los árboles
        # recibidos en el paso anterior (en caso de que más de una
        # producción esté asociada al mismo NT, los uno con OperandoUnion).
        for p in lineas:
            nt = p[0]
            prod = p[1]
            if nt.simbolo in self.producciones:
                self.producciones[nt.simbolo] = OperandoUnion(self.producciones[nt.simbolo], prod)
            else:
                self.producciones[nt.simbolo] = prod
